package com.atwy.sort;

/**
 * 关键在partition，如何分区，快速排序最坏的情况是O(N^2),就是分区得到的退化后的链表
 * 最好情况下，每次 partition 函数切分出的 p 都恰好是正中间索引 (lo + hi) / 2（二分），
 * 且每次切分之后会到左边或者右边的子数组继续进行切分，那么 partition 函数执行的次数是 logN，每次输入的数组大小缩短一半。
 * 所以总的时间复杂度为：
 * # 等比数列求和公司，取极限
 * N + N/2 + N/4 + N/8 + ... + 1 = 2N = O(N)
 *
 *
 * 三指针法解决快速排序中大量重复元素的导致性能降低的问题
 */
public class QuickSorting2 {

    public static void main(String[] args) {

        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        array = new int[]{1,2,1,1,1,3};
        new QuickSorting2().sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        /*int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));*/

    }

    public void sort(int[] arry) {
        quickSort(arry, 0, arry.length - 1);
    }
    /**
     * 看看这里的框架 和二叉树的前序遍历是不是一样的，
     *
     * 快速排序是先将一个元素排好序，然后再将剩下的元素排好序。
     *
     * partition 函数干的事情，其实就是把 nums[p] 这个元素排好序了。
     * @param arry
     * @param start
     * @param end
     */
    public void quickSort(int[] arry, int start, int end) {
        // 递归结束条件
        if (start >= end) {
            return;
        }

        // 先分区，找到基准点
        // 将数组分为三部分，[start,p[0]-1] < [p[0],p[1]] < [p[1]+1,end]
        // 其中 [p[0],p[1]]指的是 p[0],p[1]之间包含边界都是相等的元素
        // 然后就是左小 右大，中间相等，每次分区都是把基准值及与基准值相等的元素放好位置，后序只需对左右再排序，递归下去就可以了
        int[] p = partition2(arry, start, end);
        // 分区进行递归
        quickSort(arry, start, p[0]-1);
        quickSort(arry, p[1]+1, end);
    }

    /**
     * partition的目的是 把基准值放在正确的位置，
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public int[] partition(int[] nums,int start,int end){
        // 目的：找到两个位置left，right，把数组分成3部分，左边小于，中间等于，右边大于
        // 三指针法
        // left在最左边，往右边移动
        // right在最右边，往左边移动
        // mid从最左边往右边进行整个数组的遍历，遇到right指针时就是遍历了整个数组
        int base = nums[start];
        int left = start;
        int mid = start+1;
        int right = end+1;
        // 结束条件 mid==right，遍历结束，(left,right)之间就是基准值的位置
        while (mid<right){
            if(nums[mid]>base){ // 将nums[mid]交换到[right,end]之间
                // 将大数交换到右边去
                right--;
                swap(nums,mid,right);
                // 指针先移动，再操作，此时指针指向的是当前操作的值
                // 可以理解为，先准备好位置，然后放数据
                // 如果这样做的话，在初始化指针时，需要指针先“退”一步，如果right在后序操作是--，则初始化时right取边界值+1 = end+1

            }else if(nums[mid]<base){// 将nums[mid]交换到[start+1,left]之间
                // 交换到左边去
                left++;
                if(left!=mid){
                    swap(nums,mid,left);
                }
                mid++;
            }else {
                mid++;
            }
        }
        // 结束循环，left指向小于base的值，right指向大于base的值，且[left+1,right-1] 区间的值就是等于base的值
        swap(nums,start,left);
        // 做了交换之后，left指向等于base的值了
        return new int[]{left,right-1};
    }

    public int[] partition2(int[] nums,int start,int end){
        int base = nums[start];
        // 起始位置为基准值，最后再操作
        int left = start+1;
        int mid = start+1;
        int right = end+1;
        // 如果是先操作数据，再移动指针，则循环结束，所有的基准值是落在 [left,right]区间
        // mid是遍历数组的指针，理论上mid应该最终等于right（如果right=end），此时循环结束条件是 mid = right + 1，这样做不太好控制边界了
        // 所以让right = end+1;循环退出条件是 mid = right;如果这样在操作right指针之前，先让right减一，提供位置。
        while (mid < right){
            if(nums[mid]>base){
                right--;
                swap(nums,mid,right);
            }else if(nums[mid]<base){
                if(left != mid){
                    swap(nums,mid,left);
                }
                left++;
                mid++;
            }else {
                mid++;
            }
        }
        swap(nums,start,left-1);

        return new int[]{left-1,right-1};
    }

    void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
